package algorithm.union;

/**
 * @author bingo
 * @Description    并查集的优化，基于路径压缩的优化
 * @Date 2018/6/23
 */
public class UnionFind5 {

    private int[] parent;

    private int count;

    private int[] rank;

    public UnionFind5(int n) {
        parent = new int[n];
        rank = new int[n];
        count = n;
        for(int i=0;i<n;i++){
            parent[i] = i;
            rank[i] = 1;
        }
    }

    /**
     *          0 1 2 3 4 5 6 7 8 9
     *          ------------------------
     * parent： 0 1 2 3 4 5 6 7 8 9
     *
     *          0 1 2 3 4 5 6 7 8 9
     *          ------------------------
     * parent： 0 0 1 3 4 5 6 7 8 9
     *
     * */

    /**找到根节点*/
    public int find(int p){
        assert p >=0 && p<count;
        /**路径压缩方式一*/
    /*while(parent[p]!=p){
            parent[p] = parent[parent[p]];
            p=parent[p];
        }*/
      /**路径压缩方式二*/
        while(parent[p]!=p){
            parent[p] = find(parent[p]);
            p=parent[p];
        }


        return p;
    }

    /**判断他们的根是否相连*/
    public boolean isConnected(int p,int q){

        return  find(p)==find(q);

    }

    public void unionElements(int p,int q){

        int pRoot = find(p);
        int qRoot = find(q);
        if(pRoot==qRoot){
            return;
        }
        if(rank[pRoot]<rank[qRoot]){
            parent[pRoot] = qRoot;
        }else if(rank[qRoot]<rank[pRoot]){
            parent[qRoot] = pRoot;
        }else{
            parent[pRoot] = qRoot;
            rank[qRoot]++;
        }
    }

    public static void main(String[] args) {
        UnionFind5 unionFind4 = new UnionFind5(10);
        for(int i=0;i<10;i++){
            System.out.print(unionFind4.parent[i]+",");
        }
        System.out.println();
        unionFind4.unionElements(1,0);
        unionFind4.unionElements(2,1);
        unionFind4.unionElements(2,3);
        unionFind4.unionElements(3,4);
        unionFind4.unionElements(4,4);
        unionFind4.unionElements(5,5);
        unionFind4.unionElements(7,8);
        unionFind4.unionElements(8,9);
        for(int i=0;i<10;i++){
            System.out.print(unionFind4.parent[i]+",");
        }
    }

}
